package com.kaifamiao.month03.day0328;

public class Sort2 {

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 1, 4};
//        quickSort(arr, 0, arr.length - 1);  // 快排
//        insertSort(arr); // 插入排序
//        selectSort(arr); // 选择排序
        bubbleSort(arr); // 冒泡排序
        for(int a : arr){
            System.out.print(a);
        }
    }

    /**
     * 快排
     * @param arr 需要排序的数组
     * @param left 左边的位置
     * @param right 右边的位置
     */
    public static void quickSort(int[] arr, int left, int right){
        if(left < right){
            int mid = getMid(arr, left, right);
            quickSort(arr, left , mid - 1);
            quickSort(arr, mid + 1, right);
        }
    }

    /**
     * 每次循环确认一个基准的位置
     * @param arr 循环查找的数组
     * @param left 每次开始的位置
     * @param right 结束的位置
     * @return 每次循环确认的基准的位置下标
     */
    public static int getMid(int[] arr, int left, int right){
        int temp = arr[left];
        while(left < right){
            while(arr[right] >= temp && left < right){ // 如果右边的数字比当前的大，不用管，如果小，换位置
                right --;
            }
            arr[left] = arr[right];
            while(arr[left] <= temp && left < right){ // 如果左边的数字比当前的数字小，不用管，如果大 换位置
                left ++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }

    /**
     * 插入排序  当前的跟前面的所有比较，如果当前的小于前面的，前面的往后面放
     */
    public static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i ++){
            int current = arr[i];
            int j = i - 1;
            while(j >= 0 && arr[j] > current){
                arr[j + 1] = arr[j];
                j --;
            }
            arr[j + 1] = current;
        }
    }

    /**
     * 选择排序
     * 先假设第一个是最小的，跟后面的进行判断，找到最小的，替换位置，把最小的放到第一个，以此类推
     * @param arr 需要排序的数组
     */
    public static void selectSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i ++){
            int minIndex = i; // 假设第一个是最小的
            for(int j = minIndex + 1; j < arr.length; j ++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }   // 循环结束找到最小值的下标，跟当前认为的最小的替换位置
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    /**
     * 两两比较 如果后面的大于前面的交换位置，每轮循环确定一个最大的
     * @param arr 需要排序的数组
     */
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i ++){
            for(int j = 0; j < arr.length - 1 - i; j ++){
                if(arr[j] > arr[ j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
